BZOJ 1826 缓存交换

Description

在计算机中,CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时,则需要从主存里把数据调入Cache。此时,如果Cache容量已满,则必须先从中删除一个。 例如,当前Cache容量为3,且已经有编号为10和20的主存单元。 此时,CPU访问编号为10的主存单元,Cache命中。 接着,CPU访问编号为21的主存单元,那么只需将该主存单元移入Cache中,造成一次缺失(Cache Miss)。 接着,CPU访问编号为31的主存单元,则必须从Cache中换出一块,才能将编号为31的主存单元移入Cache,假设我们移出了编号为10的主存单元。 接着,CPU再次访问编号为10的主存单元,则又引起了一次缺失。我们看到,如果在上一次删除时,删除其他的单元,则可以避免本次访问的缺失。 在现代计算机中,往往采用LRU(最近最少使用)的算法来进行Cache调度——可是,从上一个例子就能看出,这并不是最优的算法。 对于一个固定容量的空Cache和连续的若干主存访问请求,聪聪想知道如何在每次Cache缺失时换出正确的主存单元,以达到最少的Cache缺失次数。

Input

输入文件第一行包含两个整数N和M(1<=M<=N<=100,000),分别代表了主存访问的次数和Cache的容量。 第二行包含了N个空格分开的正整数,按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。

Output

输出一行,为Cache缺失次数的最小值。

Sample Input

6 2
1 2 3 1 2 3

Sample Output

4

Hint

在第4次缺失时将3号单元换出Cache。

Solution

脑补一下肯定是下一个相同元素近的更优(保留)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>

#define maxn 100000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

struct disct{
int v,id;
}disc[maxn];

priority_queue<pii,vector<pii>,less<pii> > q;
int Next[maxn],last[maxn],ins[maxn];
int a[maxn],pos[maxn],cnt,num;
int n,m,ans;

bool comp(disct a,disct b)
{

return a.v<b.v;
}

void DP()
{

for(int i=1;i<=n;i++){
if( last[pos[i]] ) Next[last[pos[i]]]=i;
last[pos[i]]=i,Next[i]=n+1;
}
for(int i=1;i<=n;i++)
if( !ins[pos[i]] ){
ans++;
if( num>=m ){
pii sd=q.top();q.pop();
if( ins[sd.second] ) ins[sd.second]=0,num--;
}
if( ins[pos[i]]==0 ) ins[pos[i]]=1,num++;
q.push((pii){Next[i],pos[i]});
}
else q.push((pii){Next[i],pos[i]});
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1826.in","r",stdin);
freopen("1826.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
disc[i].v=a[i],disc[i].id=i;
}
sort(disc+1,disc+n+1,comp);
disc[0].v=-1;
for(int i=1;i<=n;i++){
if( disc[i].v!=disc[i-1].v ) cnt++;
pos[disc[i].id]=cnt;
}
DP();
printf("%d",ans);
return 0;
}